package backTrack;

import java.util.Iterator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 37. 解数独
 */
public class P37 {
    public void solveSudoku(char[][] board) {
        backTrack(board, 0);
    }

    private void showMatrix(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                System.out.print(board[i][j] + ",");
            }
            System.out.println();
        }
    }

    private boolean backTrack(char[][] board, int pos) {
        if (pos == board.length * board.length) {
            return true;
        } else {
            int row = pos / board.length;
            int col = pos % board.length;
            if (board[row][col] != '.') {
                return backTrack(board, pos + 1);
            } else {
                // 依次遍历
                List<Integer> nums = possibleNum(board, row, col);
                for (int num : nums) {
                    board[row][col] = (char) ('0' + num);
                    boolean flag = backTrack(board, pos + 1);
                    if (flag) {
                        return true;
                    }
                    board[row][col] = '.';
                }
            }
            return false;
        }
    }

    public List<Integer> possibleNum(char[][] board, int row, int col) {
        List<Integer> range = IntStream.rangeClosed(1, 9).mapToObj(a -> a).collect(Collectors.toList());
        // 行
        for (int i = 0; i < 9; i++) {
            if (board[row][i] != '.') {
                delVal(range, Integer.valueOf(board[row][i] + ""));
            }
        }
        // 列
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.') {
                delVal(range, Integer.valueOf(board[i][col] + ""));
            }
        }
        // 格子
        int grid_row = row / 3;
        int grid_col = col / 3;
        for (int r = grid_row * 3; r < (grid_row + 1) * 3; r++) {
            for (int c = grid_col * 3; c < (grid_col + 1) * 3; c++) {
                if (board[r][c] != '.') {
                    delVal(range, Integer.valueOf(board[r][c] + ""));
                }
            }
        }
        return range;
    }

    private void delVal(List<Integer> range, int val) {
        Iterator<Integer> iterator = range.iterator();
        while (iterator.hasNext()) {
            if (val == iterator.next()) {
                iterator.remove();
                break;
            }
        }
    }

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        new P37().solveSudoku(board);
    }
}
